package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

import java.util.Arrays;

/**
 *  题解：
 *  https://leetcode.cn/problems/longest-palindromic-subsequence/solutions/67456/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/
 */
public class 最长回文子序列 {

    int[][] mem;
    public int longestPalindromeSubseq(String s) {

        if (s == null){
            return 0;
        }
        if (s.length()<2){
            return 1;
        }

        char[] chars = s.toCharArray();
         mem = new int[chars.length][chars.length];
        for (int[] ints : mem) {
            Arrays.fill(ints,-1);
        }
        return longestPalindromeSubseqDFS(chars,0,chars.length-1);
    }

    public int longestPalindromeSubseq_dynamic(String s) {
        
        //定义dp， dp[i][j] 表示s[i..j] 的最长回文子序列
        int[][] dp = new int[s.length()][s.length()];
        
        //base case
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] =1;
        }
        // 状态转移方程  s[i] == s[j] 则 dp[i][j] = dp[i+1][j-1] +2 
        // ,s[i] != s[j] 则 dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
        int n = s.length();
        char[] chars = s.toCharArray();

        for (int i = n-2; i >=0; i--) {
            for (int j = i+1; j < n; j++) {

                if (chars[i] == chars[j]){
                    dp[i][j] = dp[i+1][j-1] +2;
                }else {
                    dp[i][j] =  Math.max(dp[i+1][j],dp[i][j-1]);
                }

            }
        }

        return dp[0][n-1];
    }




    public int longestPalindromeSubseqDFS(char[] chars,int i,int j){

        if (mem[i][j] != -1){
            return mem[i][j];
        }

        if (i>= chars.length || j< 0){
            return 0;
        }

        if (i>j){
            return 0;
        }

        //此时字符串只有一个，长度返回1
        if (i == j){
            mem[i][j] = 1;
            return mem[i][j];
        }



        if (chars[i] == chars[j]){
            mem[i][j]  = longestPalindromeSubseqDFS(chars,i+1,j-1)+2;
        }else {

            mem[i][j]  = Math.max(longestPalindromeSubseqDFS(chars,i,j-1)
                    ,longestPalindromeSubseqDFS(chars,i+1,j));
        }
        return mem[i][j];
    }



}
